package leetcode_400;

import java.util.Arrays;

/**
 *@author 周杨
 *CombinationSumIV_377 给定一个数组和一个target 求数组中有多少组合能组成target
 *describe:回溯法超时  用动态规划 每次保存当前有多少组合  先排序可以优化算法 AC 99%
 *2018年7月10日 下午5:03:51
 */
public class CombinationSumIV_377 {
	int res=0;
	int nums[];
	int target;
	public static void main(String[] args) {
		CombinationSumIV_377 test=new CombinationSumIV_377();
		System.out.println(test.combinationSum4_(new int[] {1,2,3}, 4));
		//System.out.println(test.combinationSum4(new int[] {1,2,3}, -1));

	}
	
	public int combinationSum4(int[] nums, int target) {
        this.nums=nums;
        this.target=target;
        help(0);
        return this.res;
    }
	
	/**
	 * describe:回溯法 超时
	 * 2018年7月10日 下午5:04:35
	 */
	public void help(int sum) {
		if(sum>target)
			return ;
		if(sum==target) {
			++res;
			return ;
		}
		for(int i=0;i<nums.length;++i)
			help(sum+nums[i]);
	}
	
	/**
	 * describe:动态规划 先排序可以剪枝 AC 99%
	 * 2018年7月10日 下午5:23:00
	 */
	public int combinationSum4_(int[] nums, int target) {
        if(nums.length==0)
        	return 0;
        int []dp=new int[target+1];
        dp[0]=1;
        Arrays.sort(nums);
        for(int i=1;i<=target;++i) {
        	int res=0;
        	for(int j=0;j<nums.length;++j) {
        		if(nums[j]>i)
        			break;
        		res+=dp[i-nums[j]];
        	}
        	dp[i]=res;
        }
        return dp[target];
    }
}
